perm filename DTYPES.MSS[WHT,LSP] blob sn#756023 filedate 1984-05-12 generic text, type T, neo UTF8
@Part[Dtypes, Root = "CLM.MSS"]
@Comment{Chapter of Common Lisp Manual.  Copyright 1984 Guy L. Steele Jr.⎇


@MyChapter[Data Types]
@Label[DTYPES]

@clisp provides a variety of types of data objects.  It is important to
note that in @xlisp it is data objects that are typed, not variables.
Any variable can have any @xlisp object as its value.
(It is possible to make an explicit declaration that a variable will
in fact take on one of only a limited set of values.  However, such
a declaration may always be omitted, and the program will still run correctly.
Such a declaration merely constitutes advice from the user
that may be useful in gaining efficiency.  See @Specref[declare].)

In @clisp, a data type is a (possibly infinite) set of
@xlisp objects.  Many @xlisp objects belong to more than one
such set, and so it doesn't always make sense to ask what @i[the] type
of an object is; instead, one usually asks only whether an object belongs
to a given type.  The predicate @Funref[typep] may be used to ask
whether an object belongs to a given type,
and the function @Funref[type-of] returns @i[a] type
to which a given object belongs.

The data types defined in @clisp are arranged into a hierarchy (actually
a partial order) defined by the subset relationship.
Certain sets of objects, such as the set of numbers or the
set of strings, are interesting enough to deserve labels.
Symbols are used for most
such labels (here, and throughout this book, the word ``symbol''
refers to atomic symbols, one kind of @xlisp object,
elsewhere known as literal atoms).  See chapter
@Ref[DTSPEC] for a complete description of type specifiers.

The set of all objects is specified
by the symbol @true.  The empty data type, which contains no objects, is
denoted by @nil.  A type called @f[common] encompasses all the data
objects required by the @clisp language.  A @clisp implementation
is free to provide other data types that are not subtypes of @f[common].

The following categories of @clisp objects are of particular interest:
numbers, characters, symbols, lists, arrays, structures, and functions.
There are others as well.
Some of these categories
have many subdivisions.  There are also standard types define dto
be the union
of two or more of these categories.  The categories listed above, while they
are data types, are neither more nor less ``real'' than other data types;
they simply constitute a particularly useful slice across
the type hierarchy for expository purposes.

Here are brief descriptions various @clisp data types.
The remaining sections of this chapter go into more detail,
and also describe notations for objects
of each type.  Descriptions of @xlisp functions that operate
on data objects of each type appear in later chapters.

@Begin[Itemize]
@i[Numbers] are provided in various forms and representations.
@clisp provides a true integer data type: any integer,
positive or negative, has in principle a representation as a
@clisp data object, subject only to total memory limitations (rather than
machine word width).
A true rational data type is provided: the quotient of two integers,
if not an integer, is a ratio.
Floating-point numbers of various ranges and precisions are also
provided, as well as
Cartesian complex numbers.

@i[Characters] represent printed glyphs such as letters
or text formatting operations.  Strings are one-dimensional
arrays of characters.
@clisp provides for a rich character set, including ways to
represent characters of various type styles.

@i[Symbols] (sometimes called @i[atomic symbols] for emphasis
or clarity) are named data objects.  @xlisp provides machinery
for locating a symbol object, given its name (in the form
of a string).  Symbols have @i[property lists], which in effect
allow symbols to be treated as record structures with an extensible
set of named components, each of which may be any @xlisp object.
Symbols also serve to name functions and variables within programs.

@i[Lists] are sequences represented in the form of linked cells
called @i[conses].  There is a special object (the symbol @nil)
that is the empty list.  All other lists are built recursively by adding a new
element to the front of an existing list.  This is done by
creating a new @i[cons], which is an object having two components
called the @i[car] and the @i[cdr].  The @i[car] may hold anything,
and the @i[cdr] is made to point to the previously existing list.
(Conses may actually be used completely generally as two-element
record structures, but their most important use is to represent
lists.)

@i[Arrays] are dimensioned collections of objects.
An array can have any non-negative number of dimensions and is indexed
by a sequence of integers.  A general array can have any @xlisp object as
a component; other types of arrays are specialized for efficiency
and can hold only certain types of @xlisp objects.
It is possible for two arrays, possibly with differing dimension information,
to share the same set of elements (such that modifying one array modifies
the other also) by causing one to be @i[displaced] to the other.
One-dimensional arrays of any kind are called @i[vectors].
One-dimensional arrays of characters are called @i[strings].
One-dimensional arrays of bits (that is, of integers whose values are 0 or 1)
are called @i[bit-vectors].

@i[Hash tables] provide an efficient way of mapping any
@xlisp object (a @i[key]) to an associated object.

@i[Readtables] are used to control the built-in expression parser
@Funref[read].

@i[Packages] are collections of symbols that serve as name spaces.
The parser recognizes symbols by looking up character sequences
in the current package.

@i[Pathnames] represent names of files in a fairly implementation-independent
manner.  They are used to interface to the external file system.

@i[Streams] represent sources or sinks of data, typically characters
or bytes.  They are used to perform I/O, as well as for internal
purposes such as parsing strings.

@i[Random-states] are data structures used to encapsulate the state
of the built-in random-number generator.

@i[Structures] are user-defined record structures, objects that
have named components.  The @Macref[defstruct] facility is used
to define new structure types.  Some @clisp implementations may
choose to implement certain system-supplied data types,
such as @i[bignums], @i[readtables], @i[streams],
@i[hash tables], and @i[pathnames], as structures,
but this fact will be invisible to the user.

@i[Functions] are objects that can be invoked as procedures;
these may take arguments and return values.  (All @xlisp procedures
can be construed to return a value and therefore every procedure is
a function.)
Such objects include @i[compiled-functions] (compiled code objects).
Some functions are represented as a list whose @i[car] is a particular
symbol such as @f[lambda].  Symbols may also be used as functions.
@End[Itemize]

These categories are not always mutually exclusive.
The required relationships among the various data types are
explained in more detail in section @ref[DATA-TYPE-RELATIONSHIPS].

@Section[Numbers]

Several kinds of numbers are defined in @clisp.
They are divided into @i[integers]; @i[ratios];
@i[floating-point numbers], with names provided for
up to four different floating-point representations; and @i[complex numbers].

@Subsection[Integers]

@index[integer]
The @f[integer] data type is intended to represent mathematical integers.
Unlike most programming languages, @clisp in principle imposes no limit on
the magnitude of an integer; storage
is automatically allocated as necessary to represent large integers.

In every @clisp implementation there is a range of integers that are
represented more efficiently than others; each such integer is called a
@Def[fixnum], and an integer that is not a fixnum is called a
@Def[bignum].
@clisp is designed to hide this distinction as much as possible;
the distinction between fixnums and bignums is visible to
the user in only a few places where the efficiency of representation is
important.  Exactly which integers are
fixnums is implementation-dependent; typically they will be those
integers in the range @Minussign@;2@+[@superi[n]] to 2@+[@superi[n]]@Superminussign@;1,
inclusive, for some @i[n] not less than 15.
See @Conref[most-positive-fixnum] and @Conref[most-negative-fixnum].

Integers are ordinarily written in decimal notation, as a sequence
of decimal digits, optionally preceded by a sign and optionally followed
by a decimal point.
For example:
@lisp
@Tabclear
@Tabdivide[2]
@>0  @\;@r[Zero]
@>-0  @\;@r[This @i[always] means the same as @f[0]]
@>+6  @\;@r[The first perfect number]
@>28  @\;@r[The second perfect number]
@>1024.  @\;@r[Two to the tenth power]
@>-1  @\;@r[@i[e]@+[@SuperSail[π]@superi[i]]]
@>15511210043330985984000000.  @\;@r[25 factorial (25!), probably a bignum]
@Endlisp

@Incompatibility{@maclisp and @lmlisp normally assume that integers
are written in octal (radix-8) notation unless a decimal
point is present.
@interlisp assumes integers are written in decimal notation and uses a
trailing @f[Q] to indicate octal radix; however, a decimal point,
even in trailing position, @i[always] indicates a floating-point number.
This is of course consistent with @fortran.  @ada does not permit
trailing decimal points, but instead requires them to be embedded.
In @clisp, integers written as described
above are always construed to be
in decimal notation, whether or not the decimal point is present;
allowing the decimal point to be present permits compatibility with
@maclisp.⎇

Integers may be notated in radices other than ten.
The notation
@Lisp
@Begin[Center]
#@i[nn]r@i[ddddd]     @r[or]     #@i[nn]R@i[ddddd]
@End[Center]
@Endlisp
means the integer in radix-@i[nn] notation denoted by the digits
@i[ddddd].  More precisely, one may write @f[#], a non-empty sequence
of decimal digits representing an unsigned decimal integer @i[n],
@f[r] (or @f[R]), an optional sign, and a sequence of radix-@i[n]
digits, to indicate an integer written in radix @i[n] (which must be
between 2 and 36, inclusive).  Only legal digits
for the specified radix may be used; for example, an octal number may
contain only the digits 0 through 7.  For digits above 9,
letters of the alphabet of either
case may be used in order.  Binary, octal, and
hexadecimal radices are useful enough to warrant the special
abbreviations @f[#b] for @f[#2r], @f[#o] for @f[#8r], and
@f[#x] for @f[#16r].
For example:
@lisp
@Tabclear
@Tabdivide[2]
@>#2r11010101  @\;@r[Another way of writing @f[213] decimal]
@>#b11010101  @\;@r[Ditto]
@>#b+11010101  @\;@r[Ditto]
@>#o325  @\;@r[Ditto, in octal radix]
@>#xD5  @\;@r[Ditto, in hexadecimal radix]
@>#16r+D5  @\;@r[Ditto]
@>#o-300  @\;@r[Decimal @minussign@;192, written in base 8]
@>#3r-21010  @\;@r[Same thing in base 3]
@>#25R-7H  @\;@r[Same thing in base 25]
@>#xACCEDED  @\;@r[181202413, in hexadecimal radix]
@Endlisp

@Subsection[Ratios]

@index[ratio]
@index[rational]
A @f[ratio] is a number representing the mathematical ratio
of two integers.  Integers and ratios collectively constitute
the type @f[rational].
The canonical representation of a rational number is as an
integer if its value is integral, and otherwise as the ratio of two
integers, the @Def[numerator] and @Def[denominator], whose greatest
common divisor is one, and of which the denominator is positive (and in
fact greater than 1, or else the value would be integral).
A ratio is notated with
@f[/] as a separator, thus: @f[3/5].  It is possible to notate
ratios in non-canonical (unreduced) forms, such as @f[4/6], but the
@xlisp function @Funref[prin1] always prints the canonical form for a
ratio.

If any computation produces a result that is a ratio of
two integers such that the denominator evenly divides the
numerator, then the result is immediately converted to the equivalent
integer.  This is called the rule of @i[rational canonicalization].

Rational numbers may be written as the possibly signed quotient of
decimal numerals: an optional sign followed by two non-empty sequences of
digits separated by a @f[/].  This syntax may be described as
follows:
@Begin[Format]
@i[ratio] ::= @Mopt<@i[sign]> @Mplus<@i[digit]> @f[/] @Mplus<@i[digit]>
@End[Format]
The second sequence may not consist
entirely of zeros.
For example:
@lisp
2/3			;@r[This is in canonical form]
4/6			;@r[A non-canonical form for the same number]
-17/23			;@r[A not very interesting ratio]
-30517578125/32768	;@r[This is (@minussign@;5/2)@+[15]]
10/5			;@r[The canonical form for this is @f[2]]
@Endlisp

To notate rational numbers in radices other than ten,
one uses the same radix specifiers
(one of @f[#@i[nn]R], @f[#O], @f[#B], or @f[#X]) as for integers.
For example:
@lisp
#o-101/75		;@r[Octal notation for @f[-65/61]]
#3r120/21		;@r[Ternary notation for @f[15/7]]
#Xbc/ad                 ;@r[Hexadecimal notation for @f[188/173]]
#xFADED/FACADE          ;@r[Hexadecimal notation for @f[1027565/16435934]]
@Endlisp

@Subsection[Floating-point Numbers]

@clisp allows an implementation to provide one or more kinds of
floating-point number, which collectively make up the type @f[float].
@Index[floating-point number]
@Index2[P {number⎇, S {floating-point⎇]
A floating-point number is a (mathematical)
rational number of the form
@i[s]@centerdot@i[f]@centerdot@i[b]@+[@superi[e]@superMinussign@;@superi[p]],
where @i[s] is +1 or @minussign@;1, the @i[sign];
@i[b] is an integer greater than 1, the @i[base] or @i[radix] of the representation;
@i[p] is a positive integer, the @i[precision] (in base-@i[b] digits) of the floating-point number;
@i[f] is a positive integer between @i[b]@+[@superi[p]@superMinussign@;1] and
@i[b]@+[@superi[p]]@Minussign@;1 (inclusive), the @i[significand];
and @i[e] is an integer, the @i[exponent].
The value of @i[p] and the range of @i[e]
depends on the implementation and on the type of floating-point number
within that implementation.
In addition, there is a floating-point zero;
depending on the implementation, there may also be a ``minus zero.''
If there is no minus zero, then @f[0.0] and @f[-0.0] are
both interpreted as simply a floating-point zero.

@Implementation{The form of the above description should not be construed
to require the internal representation to be in sign-magnitude form.
Two's-complement and other representations are also acceptable.  Note
that the radix of the internal representation may be other than 2, as on
the @c[ibm] 360 and 370, which use radix 16; see
@funref[float-radix].⎇

Floating-point numbers may be provided in a variety of precisions and sizes,
depending on the implementation.  High-quality floating-point
software tends to depend critically on the precise nature of the
floating-point arithmetic, and so may not always be completely portable.
To aid in writing programs that are
moderately portable, however, certain definitions are made here:
@Begin[Itemize]
A @i[short] floating-point number (type @f[short-float])
is of the representation of smallest
fixed precision provided by an implementation.

A @i[long] floating-point number (type @f[long-float])
is of the representation of the largest fixed 
precision provided by an implementation.

Intermediate between short and long formats are two others, arbitrarily
called @i[single] and @i[double] (types @f[single-float] and @f[double-float]).
@End[Itemize]
The precise definition of these categories is implementation-dependent.
However, the rough intent is that short floating-point numbers be
precise to at least four decimal places or so (but also have
a space-efficient representation);
single floating-point numbers, to at least seven decimal places;
and double floating-point numbers, to at least fourteen decimal places.
It is suggested that
the precision (measured in ``bits,'' computed as @i[p] log@-[2]@i[b])
and the exponent size (also measured in ``bits,'' computed as the base-2
logarithm of one plus the maximum exponent value) be at least as great
as the values in Table @Ref[Floating-Format-Requirements-Table].
@Begin[Table]
@mline[]
@Caption[Recommended Minimum Floating-Point Precision and Exponent Size]
@Tag[Floating-Format-Requirements-Table]
@Begin[Format]
@Tabset[+1.5 in, +1 in, +1.5 in]
@\@ux[Format@\Minimum Precision@\Minimum Exponent Size]
@\Short@\13 bits@\5 bits
@\Single@\24 bits@\8 bits
@\Double@\50 bits@\8 bits
@\Long@\50 bits@\8 bits
@End[Format]
@mline[]
@End[Table]

Floating-point numbers are written in either decimal fraction
or computerized scientific notation: an optional sign,
then a non-empty sequence of digits with an embedded decimal point,
then an optional decimal exponent specification.
If there is no exponent specifier, then
the decimal point is required, and there must be digits
after it.
The exponent specifier consists of an exponent marker,
an optional sign, and a non-empty sequence of digits.
For preciseness, here is a modified-@c[BNF] description of floating-point
notation.
@Begin[Format, group, leftmargin +0.5in]
@Tabclear
@i[floating-point-number] ::=@↑ @Mopt<@i[sign]> @Mstar<@i[digit]> @i[decimal-point] @Mplus<@i[digit]> @Mopt<@i[exponent]>
@>@mor@\ @Mopt<@i[sign]> @Mplus<@i[digit]> @Mopt{@i[decimal-point] @Mstar<@i[digit]>⎇ @i[exponent]
@i[sign] ::= @f[+] @mor @f[-]
@i[decimal-point] ::= @f[.]
@i[digit] ::= @f[0] @mor @f[1] @mor @f[2] @mor @f[3] @mor @f[4] @mor @f[5] @mor @f[6] @mor @f[7] @mor @f[8] @mor @f[9]
@i[exponent] ::= @i[exponent-marker] @Mopt<@i[sign]> @Mplus<@i[digit]>
@i[exponent-marker] ::= @f[e] @mor @f[s] @mor @f[f] @mor @f[d] @mor @f[l] @mor @f[E] @mor @f[S] @mor @f[F] @mor @f[D] @mor @f[L]
@End[Format]
If no exponent specifier is present, or if the exponent marker @f[e]
(or @f[E]) is used, then the precise format to be used is not
specified.  When such a representation is read and
converted to an internal floating-point data object, the format specified
by the variable @Varref[read-default-float-format] is used; the initial
value of this variable is @f[single-float].

The letters @f[s], @f[f], @f[d], and @f[l] (or their
respective uppercase equivalents) explicitly specify the
use of @i[short], @i[single], @i[double], and @i[long] format, respectively.

Examples of floating-point numbers:
@Lisp
0.0				;@r[Floating-point zero in default format]
0E0				;@r[Also floating-point zero in default format]
-.0				;@r[This may be a zero or a minus zero,]
				; @r[depending on the implementation]
0.				;@r[The @i[integer] zero, not a floating-point number!]
0.0s0				;@r[A floating-point zero in @i[short] format]
0s0				;@r[Also a floating-point zero in @i[short] format]
3.1415926535897932384d0		;@r[A @i[double]-format approximation to @Sail[π]]
6.02E+23			;@r[Avogadro's number, in default format]
602E+21				;@r[Also Avogadro's number, in default format]
3.1010299957f-1			;@r[log@-[10] 2, in @i[single] format]
-0.000000001s9			;@r[@i[e]@+[@superSail[π]@superi[i]] in @i[short] format, the hard way]
@Endlisp

The internal format used for an external representation depends only
on the exponent marker, and not on the number of decimal digits
in the external representation.

While @clisp provides terminology and notation sufficient
to accommodate four distinct floating-point formats,
not all implementations will have the means to support
that many distinct formats.
An implementation is therefore permitted to provide
fewer than four distinct internal floating-point formats,
in which case at least one of them will be ``shared''
by more than one of the external format names @i[short], @i[single],
@i[double], and @i[long] according to the following rules:
@Begin[Itemize]
If one internal format is provided, then it is considered to be
@i[single], but serves also as @i[short], @i[double], and @i[long].
The data types @f[short-float],
@f[single-float], @f[double-float], and @f[long-float] are
considered to be identical.  An expression such as @f[(eql 1.0s0 1.0d0)]
will be true in such an implementation
because the two numbers @f[1.0s0] and @f[1.0d0] will
be converted into the same internal format and therefore be considered
to have the same data type, despite the differing external syntax.
Similarly, @f[(typep 1.0L0 'short-float)] will be true in such
an implementation.
For output purposes all floating-point numbers are assumed to be
of @i[single] format, and so will print using the
exponent letter @f[E] or @f[F].

@Begin[Multiple]
If two internal formats are provided, then either of two correspondences
may be used, depending on which is the more appropriate:
@Begin[Itemize]
One format is @i[short]; the other is @i[single] and serves also
as @i[double] and @i[long].
The data types
@f[single-float], @f[double-float], and @f[long-float] are
considered to be identical, but @f[short-float] is distinct.
An expression such as @f[(eql 1.0s0 1.0d0)]
will be false, but @f[(eql 1.0f0 1.0d0)] will be true.
Similarly, @f[(typep 1.0L0 'short-float)] will be false,
but @f[(typep 1.0L0 'single-float)] will be true.
For output purposes all floating-point numbers are assumed to be
of @i[short] or @i[single] format.

One format is @i[single] and serves also as @i[short];
the other is @i[double] and serves also as @i[long].
The data types @f[short-float] and @f[single-float] are considered to be
identical, and the data types @f[double-float] and @f[long-float] are
considered to be identical.
An expression such as @f[(eql 1.0s0 1.0d0)]
will be false, as will @f[(eql 1.0f0 1.0d0)];
but @f[(eql 1.0d0 1.0L0)] will be true.
Similarly, @f[(typep 1.0L0 'short-float)] will be false,
but @f[(typep 1.0L0 'double-float)] will be true.
For output purposes all floating-point numbers are assumed to be
of @i[single] or @i[double] format.
@End[Itemize]
@End[Multiple]

@Begin[Multiple]
If three internal formats are provided, then either of two correspondences
may be used, depending on which is the more appropriate:
@Begin[Itemize]
One format is @i[short]; another format is @i[single]; and the third format is
@i[double] and serves also as @i[long].  Similar constraints apply.

One format is @i[single] and serves also as @i[short];
another is @i[double]; and the third format is @i[long].
@End[Itemize]
@End[Multiple]
@End[Itemize]

@Implementation{It is recommended that an implementation
provide as many distinct floating-point formats as feasible,
given Table @ref[Floating-Format-Requirements-Table] as a guideline.
Ideally, short-format floating-point numbers should have an
``immediate'' representation that does not require heap allocation;
single-format
floating-point numbers should approximate @c[IEEE] proposed standard
single-format floating-point numbers; and double-format floating-point
numbers should approximate @c[IEEE] proposed standard double-format
floating-point numbers
@Cite[IEEE-PROPOSED-FLOATING-POINT-STANDARD,
IEEE-FLOATING-POINT-IMPL-GUIDE,
IEEE-FLOATING-POINT-IMPL-GUIDE-ERRATA].⎇


@Subsection[Complex Numbers]

Complex numbers (type @f[complex])
are represented in Cartesian form, with a real part and an imaginary
part each of which is a non-complex number (integer, ratio, or floating-point
number).  It should be emphasized that the parts of a complex
number are not necessarily floating-point numbers; in this, @clisp
is like @pl1 and differs from @fortran.  However, both parts must
be of the same type: either both are rational, or both are of the
same floating-point format.

Complex numbers may be notated by writing the characters @f[#C]
followed by a list of the real and imaginary parts.
If the two parts as notated are not of the same type, then
they are converted according to the rules of floating-point contagion
as described in chapter @ref[NUMBER].
(Indeed, @f[#C(@i[a] @i[b])] is equivalent to @f[#,(complex @i[a] @i[b])];
see the description of the function @Funref[complex].)
For example:
@lisp
#C(3.0s1 2.0s-1)
#C(5 -3)	;@r[A Gaussian integer]
#C(5/3 7.0)	;@r[Will be converted internally to @f[#C(1.66666 7.0)]]
#C(0 1)		;@r[The imaginary unit, that is, @i[i]]
@Endlisp

The type of a specific complex number is indicated by a list
of the word @f[complex] and the type of the components; for example,
a specialized representation for complex numbers with short floating-point
parts would be of type @f[(complex short-float)].  The type @f[complex]
encompasses all complex representations.

A complex number of type @f[(complex rational)], that is, one whose
components are rational, can never have a zero imaginary part.
If the result of any computation would be a complex rational
with a zero imaginary part, the result is immediately
converted to a non-complex rational number by taking the
real part.  This is called the rule of @i[complex canonicalization].
This rule does not apply to complex numbers whose parts are floating-point
numbers; @f[#C(5.0 0.0)] and @f[5.0] are different.

@Section[Characters]

Characters are represented as data objects of type @f[character].
There are two subtypes of interest,
called @f[standard-char] and @f[string-char].

A character object can be notated by writing @f[#\] followed
by the character itself.  For example, @f[#\g] means the character
object for a lowercase g.  This works well enough for printing
characters.  Non-printing characters have names, and can be notated
by writing @f[#\] and then the name; for example, @f[#\Space]
(or @f[#\SPACE] or @f[#\space] or @f[#\sPaCE])
means the space character.  The syntax for character names after @f[#\]
is the same as that for symbols.  However, only character names
that are known to the particular implementation may be used.

@Subsection[Standard Characters]

@clisp defines a ``standard character set'' (subtype @f[standard-char])
for two purposes.
@clisp programs that are @i[written in] the standard character set
can be read by any @clisp implementation; and @clisp programs
that @i[use] only standard characters as data objects are most likely
to be portable.  The @clisp character set consists of a space character
@f[#\Space], a newline character @f[#\Newline], and these ninety-four
non-blank printing characters or their equivalents:
@Lisp
@;  ! " # $ % & ' ( ) * + , - . / 0 1 2 3 4 5 6 7 8 9 : ; < = > ?
@@ A B C D E F G H I J K L M N O P Q R S T U V W X Y Z @lbracket \ @rbracket ↑ @underscore
@bq a b c d e f g h i j k l m n o p q r s t u v w x y z @lbrace | @rbrace @tilde
@Endlisp
The @clisp standard character set is apparently equivalent to
the ninety-five standard ASCII printing characters plus a newline character.
Nevertheless, @clisp is designed to be relatively independent of
the ASCII character encoding.  For example, the collating sequence
is not specified except to say that digits must be properly ordered,
the uppercase letters must be properly ordered, and
the lowercase letters must be properly ordered
(see @Xfunref[X {char<⎇, L {char#&L⎇] for a precise specification).
Other character encodings, particularly EBCDIC, should be easily accommodated
(with a suitable mapping of printing characters).

Of the ninety-four non-blank printing characters, the following are
used in in only limited ways in the syntax of @clisp programs:
@lisp
@lbracket  @rbracket  @lbrace  @rbrace  ?  !  ↑  @underscore  @tilde  $  %
@endlisp
All of these characters except @f[!] and @f[@underscore] are used within
@f[format] strings as formatting directives.
Except for this,
@f{@lbracket⎇, @f{@rbracket⎇, @f[@lbrace], @f[@rbrace],
@f[?], and @f[!] are not used in @clisp and are reserved to the user
for syntactic extensions; @f[↑] and @f[@underscore] are not yet used in @clisp,
but are part of the syntax of reserved tokens,
and are reserved to implementors;
@f[@tilde] is not yet used in @clisp, and reserved to implementors;
and @f[$] and @f[%] are normally regarded as alphabetic characters,
but are not used in the names of any standard @clisp functions,
variables, or other entities.

The following characters are called @i[semi-standard]:
@lisp
#\Backspace    #\Tab    #\Linefeed    #\Page    #\Return    #\Rubout
@endlisp
Not all implementations of @clisp need to support them; but those
implementations that
use the standard ASCII character set should support them, treating them as
corresponding respectively to the ASCII characters @c[BS] (octal code 010),
@c[HT] (011), @c[LF] (012), @c[FF] (014), @c[CR] (015), and @c[DEL] (177).
These characters are not
members of the subtype @f[standard-char] unless synonymous with
one of the standard characters specified above.
For example, in a given implementation it might
be sensible for the implementor to define
@f[#\Linefeed] or @f[#\Return] to be synonymous with @f[#\Newline],
or @f[#\Tab] to be synonymous with @f[#\Space].

@Subsection[Line Divisions]

The treatment of line divisions is one of the most difficult issues
in designing portable software, simply because there is so little agreement
among operating systems.  Some use a single character to delimit lines;
the recommended ASCII character for this purpose is the line feed character
@c[LF] (also called the new line character, @c[NL]),
but some systems use the carriage
return character @c[CR].  Much more common is the two-character sequence
@c[CR] followed by @c[LF].  Frequently line divisions have no representation
as a character but are implicit in the structuring of a file into records,
each record containing a line of text.  A deck of punched cards has this
structure, for example.

@clisp provides an abstract interface by requiring that there be a single
character, @f[#\Newline], that within the language serves as a line
delimiter.  (The language @clanguage has a similar requirement.)
An implementation of @clisp must translate between this internal
single-character representation and whatever external representation(s)
may be used.
@Implementation{How the character called @f[#\Newline] is represented
internally is not specified here, but it is strongly suggested that
the ASCII @c[LF] character be used in @clisp implementations that use the
ASCII character encoding.  The ASCII @c[CR] character is a workable,
but in most cases inferior, alternative.⎇

The requirement that a line division be represented as a single character
has certain consequences.  A character string
written in the middle of a program in such a way as to span more than
one line must contain exactly one character to represent each line division.
Consider this code fragment:
@lisp
(setq a-string "This string
contains
forty-two characters.")
@endlisp
Between @f[g] and @f[c] there must be exactly one character,
@f[#\Newline]; a two-character sequence, such as @f[#\Return] and then
@f[#\Newline], is not acceptable, nor is the absence of a character.
The same is true between @f[s] and @f[f].

When the character @f[#\Newline] is written to an output file,
the @clisp implementation must take the appropriate action
to produce a line division.  This might involve writing out a
record or translating @f[#\Newline] to a @c[CR]/@c[LF] sequence.
@Implementation{If an implementation uses the ASCII character encoding,
uses the @c[CR]/@c[LF] sequence externally to delimit lines,
uses @c[LF] to represent @f[#\Newline] internally, and supports @f[#\Return]
as a data object corresponding to the ASCII character @c[CR], the
question arises as to what action to take when the program
writes out @f[#\Return] followed by @f[#\Newline].
It should first be noted that @f[#\Return] is not a standard @clisp
character, and the action to be taken when @f[#\Return] is written out
is therefore not defined by the @clisp language.  A plausible approach
is to buffer the @f[#\Return] character, and suppress it if and only if the
next character if @f[#\Newline] (the net effect is to generate a @c[CR]/@c[LF]
sequence).
Another plausible
approach is simply to ignore
the difficulty and declare that writing @f[#\Return] and then
@f[#\Newline] results in the sequence @c[CR]/@c[CR]/@c[LF] in the output.⎇

@Subsection[Non-standard Characters]

Any implementation may provide additional characters, whether printing
characters or named characters.  Some plausible examples:
@lisp
#\@sail[π]    #\@sail[α]    #\Break    #\Home-Up   #\Escape
@endlisp
The use of such characters may render @clisp programs non-portable.

@Subsection[Character Attributes]

Every object of type @f[character]
has three attributes: @i[code], @i[bits], and @i[font].
The code attribute is intended to distinguish among the printed glyphs
and formatting functions for characters; it is a numerical encoding
of the character proper.
The bits attribute allows extra
flags to be associated with a character.  The font attribute permits
a specification of the style of the glyphs (such as italics).
Each of these attributes may be understood to be a non-negative integer.

The font attribute may be notated in unsigned decimal notation
between the @f[#] and the @f[\].  For example,
@f[#3\a] means the letter @f[a] in font 3.
This might mean the same thing as @f[#\@sail[α]] if font 3
were used to represent Greek letters.
Note that not all @clisp implementations provide for non-zero
font attributes; see @Conref[char-font-limit].

The bits attribute may be notated
by preceding the name of the character by the names or initials
of the bits,
separated by hyphens.  The character itself may be written
instead of the name, preceded if necessary by @f[\].  For example:
@Lisp
@Tabdivide[2]
#\Control-Meta-Return@\#\Meta-Control-Q
#\Hyper-Space@\#\Meta-\a
#\Control-A@\#\Meta-Hyper-\:
#\C-M-Return@\#\Hyper-\@Sail[π]
@Endlisp
Note that not all @clisp implementations provide for non-zero
bits attributes; see @Conref[char-bits-limit].

@Subsection[String Characters]

Any character whose bits and font attributes are zero may be contained
in strings.  All such characters together constitute a subtype of
the characters; this subtype is called @f[string-char].

@Section[Symbols]

Symbols are @xlisp data objects that serve several purposes
and have several interesting characteristics.  Every object of
type @f[symbol] has a name,
called its @i[print name].  Given a symbol, one can
obtain its name in the form of a string.  Conversely,
given the name of a symbol as a string one can obtain the
symbol itself.  (More precisely, symbols are organized into
@i[packages], and all the symbols in a package are uniquely
identified by name.  See chapter @ref[XPACK].)

Symbols have a component called the @i[property list], or @i[plist].
By convention this is always a list whose even-numbered
components (calling the first component zero) are symbols,
here functioning as property names, and whose odd-numbered components
are associated property values.  Functions are provided for manipulating
this property list; in effect, these allow a symbol to be treated as an
extensible record structure.

Symbols are also used to represent certain kinds of variables in @xlisp
programs, and there are functions for dealing with the values associated
with symbols in this role.

A symbol can be notated simply by writing its name.
If its name is not empty, and if the name consists only of
uppercase alphabetic, numeric, or certain ``pseudo-alphabetic''
special characters (but not
delimiter characters such as parentheses or space), and if
the name of the symbol cannot be mistaken for a number, then
the symbol can be notated by the sequence of characters in its name.
Any uppercase letters that appear in the (internal) name may
be written in either case in the external notation (more on this below).
For example:
@lisp
@Tabset[+24]
FROBBOZ@\;@r[The symbol whose name is @f[FROBBOZ]]
frobboz@\;@r[Another way to notate the same symbol]
fRObBoz@\;@r[Yet another way to notate it]
unwind-protect@\;@r[A symbol with a @f[-] in its name]
+$@\;@r[The symbol named @f[+$]]
1+@\;@r[The symbol named @f[1+]]
+1@\;@r[This is the integer 1, not a symbol.]
pascal@underscore@;style@\;@r[This symbol has an underscore in its name.]
b↑2-4*a*c@\;@r[This is a single symbol!]
@\;  @r[It has several special characters in its name.]
file.rel.43@\;@r[This symbol has periods in its name.]
/usr/games/zork@\;@r[This symbol has slashes in its name.]
@Endlisp
In addition to letters and numbers, the following characters are normally
considered to be ``alphabetic'' for the purposes of notating
symbols:
@Begin[Verbatim]
+  -  *  /  @@  $  %  ↑  &  @underscore@;  =  <  >  @tilde  .
@End[Verbatim]
Some of these characters have conventional purposes for naming things;
for example, symbols that name special variables
generally have names beginning and ending with
@f[*].  The last character listed above, the period, is considered alphabetic
@i[provided] that a token does not consist entirely of periods.
A single period standing by itself is used in the notation
of conses and dotted lists; a token consisting of two or more periods
is syntactically illegal.  (The period also serves as the decimal point
in the notation of numbers.)

The following characters are also alphabetic by default, but are explicitly
reserved to the user for definition as reader macro characters
(see section @Ref[MACRO-CHARACTERS-SECTION]) or any other desired purpose,
and therefore should not be used routinely in names of symbols:
@Begin[Verbatim]
?  !  @lbracket  @rbracket  @lbrace  @rbrace
@End[Verbatim]

A symbol may have uppercase letters, lowercase letters, or both
in its print name.
However, the @xlisp reader normally converts lowercase letters to
the corresponding uppercase letters when reading symbols.
The net effect is that most of the time case makes no
difference when @i[notating] symbols.  Case @i[does] make
a difference internally and when printing a symbol.
Internally the symbols that name all standard @clisp functions,
variables, and keywords have uppercase names; their names appear
in lower case in this manual for readability.  Typing such names
with lowercase letters works because the function @f[read] will convert
lowercase letters to the equivalent uppercase letters.

If a symbol cannot be simply notated by the characters of its name
because the (internal) name contains special characters or lowercase letters,
then there are two ``escape'' conventions for notating them.
Writing a @f[\] character before any character causes the character
to be treated itself as an ordinary character for use in a symbol name;
in particular, it suppresses internal conversion of lowercase letters
to their uppercase equivalents.
If any character in a notation is preceded by @f[\], then that
notation can never be interpreted as a number.
For example:
@lisp
@tabset[+24]
\(@\;@r[The symbol whose name is @f[(]]
\+1@\;@r[The symbol whose name is @f[+1]]
+\1@\;@r[Also the symbol whose name is @f[+1]]
\frobboz@\;@r[The symbol whose name is @f[fROBBOZ]]
3.14159265\s0@\;@r[The symbol whose name is @f[3.14159265s0]]
3.14159265\S0@\;@r[A different symbol, whose name is @f[3.14159265S0]]
3.14159265s0@\;@r[A short-format floating-point approximation to @Sail[π]]
APL\\360@\;@r[The symbol whose name is @f[APL\360]]
apl\\360@\;@r[Also the symbol whose name is @f[APL\360]]
\(b↑2\)\ -\ 4*a*c@\;@r[The name is @f[(B↑2) - 4*A*C].]
@\;  @r[It has parentheses and two spaces in it.]
\(\b↑2\)\ -\ 4*\a*\c@\;@r[The name is @f[(b↑2) - 4*a*c].]
@\;  @r[The letters are explicitly lowercase.]
@Endlisp
It may be tedious to insert a @f[\] before @i[every] delimiter
character in the name of a symbol if there are many of them.
An alternative convention is to surround the name of a symbol
with vertical bars; these cause every character between them to
be taken as part of the symbol's name, as if @f[\] had been written
before each one, excepting only
@f[|] itself and @f[\], which must nevertheless be preceded by @f[\].
For example:
@lisp
@tabset[+24]
|"|@\;@r[The same as writing @f[\"]]
|(b↑2) - 4*a*c|@\;@r[The name is @f[(b↑2) - 4*a*c]]
|frobboz|@\;@r[The name is @f[frobboz], not @f[FROBBOZ]]
|APL\360|@\;@r[The name is @f[APL360], because]
@\;  @r[the @f[\] quotes the @f[3],]
|APL\\360|@\;@r[The name is @f[APL\360]]
|apl\\360|@\;@r[The name is @f[apl\360]]
|\|\||@\;@r[Same as @f[\|\|]: the name is @f[||]]
|(B↑2) - 4*A*C|@\;@r[The name is @f[(B↑2) - 4*A*C].]
@\;  @r[It has parentheses and two spaces in it.]
|(b↑2) - 4*a*c|@\;@r[The name is @f[(b↑2) - 4*a*c].]
@Endlisp

@Section[Lists and Conses]

@index[cons]
A @f[cons] is a record structure containing two components
called the @Def[car] and the @Def[cdr].  Conses are used primarily
to represent lists.

A @Def[list] is recursively defined to be either the empty list
or a cons whose @i[cdr] component is a list.
A list is therefore a chain of conses linked by their @i[cdr] components
and terminated by @nil, the empty list.  The @i[car] components of the conses
are called the @i[elements] of the list.  For each element of the list
there is a cons.  The empty list has no elements at all.

A list is notated by writing the elements of the list in order,
separated by blank space (space, tab, or return characters),
and surrounded by parentheses.
For example:
@lisp
(a b c)			;@r[A list of three symbols]
(2.0s0 (a 1) #\*)	;@r[A list of three things: a short floating-point number,]
			;  @r[another list, and a character object]
@Endlisp
The empty list @nil therefore can be written as @empty, because it is a list
with no elements.

A @i[dotted list] is one whose last cons does not have @nil for
its @i[cdr], rather some other data object (which is also not a cons,
or the first-mentioned cons would not be the last cons of the list).
Such a list is called ``dotted'' because of the special notation
used for it: the elements of the list are written between
parentheses as before, but after the last element and before
the right parenthesis are written a dot (surrounded by blank space)
and then the @i[cdr] of the last cons.  As a special case,
a single cons is notated by writing the @i[car] and the @i[cdr] between
parentheses and separated by a space-surrounded dot.
For example:
@lisp
(a . 4)		;@r[A cons whose @i[car] is a symbol]
		;  @r[and whose @i[cdr] is an integer]
(a b c . d)	;@r[A dotted list with three elements whose last cons]
		;  @r[has the symbol @f[d] in its @i[cdr]]
@Endlisp
@Incompatibility{In @maclisp, the dot in dotted-list notation
need not be surrounded by white space or other delimiters.
The dot is required to be delimited in @clisp, as in @lmlisp.⎇

It is legitimate to write something like @f[(a b . (c d))];
this means the same as @f[(a b c d)].  The standard @xlisp
output routines will never print a list in the first form, however;
they will avoid dot notation wherever possible.

Often the term @i[list] is used to refer either to true lists or to
dotted lists.  When the distinction is important,
the term ``true list'' will be used to refer to a list
terminated by @nil.  Most functions
advertised to operate on lists expect to be given true lists.  Throughout
this manual, unless otherwise specified, it is an error to pass a dotted
list to a function that is specified to require a list as an argument.
@Implementation{Implementors are encouraged to use the equivalent
of the predicate @Funref[endp] wherever it is necessary to test
for the end of a list.  Whenever feasible, this test should explicitly
signal an error if a list is found to be terminated by a non-@nil atom.
However, such an explicit error signal is not required, because
some such tests occur in important loops where efficiency is important.
In such cases, the predicate @Funref[atom] may be used to test
for the end of the list, quietly treating any non-@nil list-terminating
atom as if it were @nil.⎇

Sometimes the term @Def[tree] is used to refer to some cons
and all the other conses transitively accessible to it
through @i[car] and @i[cdr] links until non-conses are reached;
these non-conses are called the @i[leaves] of the tree.

Lists, dotted lists, and trees are not mutually exclusive data types;
they are simply useful points of view about structures of conses.
There are yet other terms, such as @i[association list].
None of these are true @xlisp data types.  Conses are a data type,
and @nil is the sole object of type @f[null].
The @xlisp data type @f[list] is taken to mean the union of the
@f[cons] and @f[null] data types, and therefore encompasses both
true lists and dotted lists.

@Section[Arrays]
@label[ARRAY-TYPE-SECTION]

@index[array]
An @f[array] is an object with components arranged according
to a Cartesian coordinate system.
In general, these components may be any @xlisp data objects.

The number of dimensions of an array is called its @Def[rank]
(this terminology is borrowed from @apl);
the rank is a non-negative integer.
Likewise, each dimension is itself a non-negative integer.
The total number of elements in the array is the product of all the
dimensions.

An implementation of @clisp may impose a limit on the rank of an array,
but this limit may not be smaller than 7.  Therefore, any @clisp
program may assume the use of arrays of rank 7 or less.
(A program may determine the actual limit on array ranks for
a given implementation by examining the constant @conref[array-rank-limit].)

It is permissible for a dimension to be zero.  In this case,
the array has no elements, and any attempt to access an element
is in error.  However, other properties of the array, such as the
dimensions themselves, may be used.
If the rank is zero, then there are no dimensions, and the
product of the dimensions is then by definition 1.
A zero-rank array therefore has a single element.

An array element is specified by a sequence of indices.
The length of the sequence must equal the rank of the array.
Each index must be a non-negative integer strictly less than
the corresponding array dimension.  Array indexing is
therefore zero-origin, not one-origin as in (the default case of)
@c[fortran].

As an example, suppose that the variable @f[foo] names a 3-by-5 array.
Then the first index may be 0, 1, or 2, and then second index
may be 0, 1, 2, 3, or 4.  One may refer to array elements using
the function @Funref[aref]; for example, @f[(aref foo 2 1)]
refers to element (2, 1) of the array.  Note that @f[aref] takes
a variable number of arguments: an array, and as many indices
as the array has dimensions.
A zero-rank array has no dimensions, and therefore
@f[aref] would take such an array and no indices, and return the sole
element of the array.

In general, arrays can be multidimensional,
can share their contents with other array objects, and can have their
size altered dynamically (either enlarging or shrinking) after creation.
A one-dimensional array may also have a @i[fill pointer].

Multidimensional arrays store their components in row-major order;
that is, internally a multidimensional array is stored as a one-dimensional
array, with the multidimensional index sets ordered lexicographically,
last index varying fastest.  This is important in two situations:
(1) when arrays with different dimensions share their contents, and
(2) when accessing very large arrays in a virtual-memory implementation.
(The first situation is a matter of semantics; the second, a matter
of efficiency.)

An array that is not displaced to another array, has no fill pointer, and
is not to have its size adjusted dynamically after creation is called a
@i[simple] array.  The user may provide declarations that certain arrays
will be simple.  Some implementations can handle simple arrays in an
especially efficient manner; for example, simple arrays may have a more
compact representation than non-simple arrays.

@Subsection[Vectors]

One-dimensional arrays are called @i[vectors] in @clisp
and constitute the type @f[vector] (which is therefore a subtype of @f[array]).
Vectors and lists are collectively considered to be
@i[sequences].  They differ in that any component of a one-dimensional array
can be accessed in constant time,
whereas the average component access time for a
list is linear in the length of the list; on the other hand, adding a new
element to the front of a list takes constant time, whereas the same
operation on an array takes time linear in the length of the array.

A general vector (a one-dimensional array
that can have any data object as an element, but has
no additional paraphernalia) can be notated by notating the
components in order, separated by whitespace and surrounded by @f[#(]
and @f[)].
For example:
@lisp
#(a b c)		;@r[A vector of length 3]
#(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47)
			;@r[A vector containing the primes below 50]
#()			;@r[An empty vector]
@Endlisp
Note that when the function @f[read] parses this syntax, it always constructs
a @i[simple] general vector.

@Rationale[Many people have suggested that brackets be used
to notate vectors, as @f{@lbracket@;a b c@rbracket⎇
instead of @f{#(a b c)⎇.  This notation
would be shorter, perhaps more readable, and certainly in accord with
cultural conventions in other parts of computer science and mathematics.
However, to preserve the usefulness of the user-definable macro-character
feature of the function @Funref{read⎇, it is necessary to leave some
characters to the user for this purpose.  Experience in @maclisp has
shown that users, especially implementors of languages for use
in artificial intelligence research, often want
to define special kinds of brackets.  Therefore @clisp avoids using
brackets and braces for any syntactic purpose.]

Implementations may provide certain specialized representations of
arrays for efficiency in the case where all the components are of
the same specialized (typically numeric) type.  All implementations
provide specialized arrays for the cases when the components
are characters (or rather, a special subset of the characters);
the one-dimensional instances of
this specialization are called @i[strings].
All implementations are also required to provide specialized arrays
of bits, that is, arrays of type @f[(array bit)];
the one-dimensional instances of
this specialization are called @i[bit-vectors].

@Subsection[Strings]
@label[STRING-TYPE-SECTION]

A string is simply a vector of characters.
More precisely, a string is a specialized vector whose elements
are of type @f[string-char].
The type @f[string] is therefore a subtype of the type @f[vector].
A string can be written as the sequence of characters contained in the
string, preceded and followed by a @f["] (double quote) character.
Any @f["] or @f[\] character in the sequence must additionally
have a @f[\] character before it.
For example:
@lisp
"Foo"				;@r[A string with three characters in it]
""				;@r[An empty string]
"\"APL\\360?\" he cried."	;@r[A string with twenty characters]
"|x| = |-x|"			;@r[A ten-character string]
@Endlisp
Notice that any vertical bar @f[|] in a string need not be
preceded by a @f[\].  Similarly, any double quote in the name
of a symbol written using vertical-bar notation need not be
preceded by a @f[\].  The double-quote and vertical-bar notations
are similar but distinct: double quotes indicate a character string
containing the sequence of characters,
whereas vertical bars indicate a symbol whose name is the contained
sequence of characters.

The characters contained by the double quotes, taken from left to right,
occupy locations within the string with increasing indices.
The leftmost character is string element number 0, the next one
is element number 1, and so on.

Note that the function @f[prin1] will print any character vector
(not just a simple one)
using this syntax, but the function @f[read] will always construct
a simple string when it reads this syntax.

@Subsection[Bit-Vectors]

A bit-vector can be written as the sequence of bits contained in the
string, preceded by @f[#*]; any delimiter character, such as whitespace,
will terminate the bit-vector syntax.
For example:
@lisp
#*10110				;@r[A five-bit bit-vector; bit 0 is a 1]
#*				;@r[An empty bit-vector]
@Endlisp
The bits notated following the @f[#*], taken from left to right,
occupy locations within the bit-vector with increasing indices.
The leftmost notated bit is bit-vector element number 0, the next one
is element number 1, and so on.

The function @f[prin1] will print any bit-vector (not just a simple one)
using this syntax, but the function @f[read] will always construct
a simple bit-vector when it reads this syntax.

@Section[Hash Tables]

Hash tables provide an efficient way of mapping any
@xlisp object (a @i[key]) to an associated object.
They are provided as primitives of @clisp because
some implementations may need to use internal storage
management strategies that would make it very difficult
for the user to implement hash tables himself in a portable fashion.
Hash tables are described in chapter @ref[HASH].

@Section[Readtables]

A readtable is a data structure that maps characters into syntax
types for the @xlisp expression parser.
In particular, a readtable indicates for
each character with syntax @i[macro character] what its macro
definition is.  This is a mechanism by which the user may reprogram
the parser to a limited but useful extent.
See section @ref[READTABLE-SECTION].

@Section[Packages]

Packages are collections of symbols that serve as name spaces.
The parser recognizes symbols by looking up character sequences
in the current package.  Packages can be used to hide
names internal to a module from other code.  Mechanisms are provided
for exporting symbols from a given package to the primary ``user'' package.
See chapter @ref[XPACK].

@Section[Pathnames]
Pathnames are the means by which a @clisp program can
interface to an external file system in a reasonably implementation-independent
manner.  See section @ref[PATHNAME].

@Section[Streams]

A stream is a source or sink of data, typically characters or bytes.
Nearly all functions that perform I/O do so with respect to a specified
stream.  The function @Funref[open] takes a pathname and returns a stream
connected to the file specified by the pathname.
There are a number of standard streams that are used by default for
various purposes.  See chapter @ref[STREAM].

@Section[Random-States]

An object of type @f[random-state] is used to encapsulate
state information used by the pseudo-random number generator.
For more information about @f[random-state] objects,
see section @ref[RANDOM].

@Section[Structures]

Structures are instances of user-defined data types that have
a fixed number of named components.  They are analogous to
records in @pascal.
Structures are declared using the @Macref[defstruct] construct;
@f[defstruct] automatically defines access and constructor functions for
the new data type.

Different structures may print out in different ways;
the definition of a structure type may specify a print procedure
to use for objects of that type (see the
@Kwdref[F {defstruct⎇, K {print-function⎇] option to @f[defstruct]).
The default notation for structures is:
@Lisp
#S(@i[structure-name]
	@i[slot-name-1] @i[slot-value-1]
	@i[slot-name-2] @i[slot-value-2]
		      ...)
@Endlisp
where @f[#S] indicates structure syntax, @i[structure-name] is
the name (a symbol) of the structure type, each @i[slot-name] is the name
(also a symbol) of a component, and each corresponding @i[slot-value]
is the representation of the @xlisp object in that slot.

@Section[Functions]

A @i[function] is anything that may be correctly given to the @Funref[funcall]
or @Funref[apply] function, and is
to be executed as code when arguments are supplied.

A @i[compiled-function] is a compiled code object.

A lambda-expression
(a list whose @i[car] is the symbol @f[lambda]) may serve as a function.
Depending on the implementation, it may be possible for other lists to
serve as functions.  For example, an implementation might choose to
represent a ``lexical closure'' as a list whose @i[car] contains some
special marker.

A symbol may serve as a function; an attempt to invoke a symbol as a function
causes the contents of the symbol's function cell to be used.
See @Funref[symbol-function] and @Macref[defun].

The result of evaluating a @specref[function] special form
will always be a function.

@Section[Unreadable Data Objects]

Some objects may print in implementation-dependent ways.
Such objects cannot necessarily be reliably reconstructed from
a printed representation, and so they are usually printed in
a format informative to the user but not acceptable to the @f[read] function:
@Lisp
#<@i[useful information]>
@Endlisp
The @xlisp reader will signal an error on encountering @f[#<].

As a hypothetical example, an implementation might print
@Lisp
#<stack-pointer si:rename-within-new-definition-maybe #o311037552>
@Endlisp
for an implementation-specific ``internal stack pointer'' data type
whose printed representation includes the name of the type,
some information about the stack slot pointed to, and the machine address
(in octal) of the stack slot.

@Section[Overlap, Inclusion, and Disjointness of Types]
@label[DATA-TYPE-RELATIONSHIPS]

The @clisp data type hierarchy is tangled and purposely left somewhat
open-ended so that implementors may experiment with new data types
as extensions to the language.  This section explicitly states all
the defined relationships between types, including subtype/supertype
relationships,
disjointness, and exhaustive partitioning.  The user of @clisp
should not depend on any relationships not explicitly stated here.
For example, it is not valid to assume that because a number
is not complex and not rational that it must be a @f[float], because
implementations are permitted to provide yet other kinds of numbers.

First we need some terminology.
If @i[x] is a supertype of @i[y], then any object of type @i[y] is also
of type @i[x], and @i[y] is said to be a subtype of @i[x].  If types
@i[x] and @i[y] are disjoint, then no object (in any implementation) may
be both of type @i[x] and of type @i[y].  Types @i[a]@-[1] through
@i[a]@-[@subi[n]] are an @i[exhaustive union] of type @i[x] if each @i[a]@-[@subi[j]]
is a subtype of @i[x], and any object of type @i[x] is
necessarily of at least one of the types @i[a]@-[@subi[j]];
@i[a]@-[1] through @i[a]@-[@subi[n]] are furthermore an @i[exhaustive partition]
if they are also pairwise disjoint.

@Begin[Itemize]
The type @f[t] is a supertype of every type whatsoever.
Every object belongs to type @f[t].

The type @nil is a subtype of every type whatsoever.
No object belongs to type @nil.

The types @f[cons], @f[symbol], @f[array], @f[number], and @f[character]
are pairwise disjoint.

The types @f[rational], @f[float], and @f[complex] are pairwise disjoint
subtypes of @f[number].

The types @f[integer] and @f[ratio] are disjoint subtypes of @f[rational].
@Rationale{It might be thought that @f[integer] and @f[ratio] should
form an exhaustive partition of the type @f[rational].  This is purposely
avoided here in order to permit compatible experimentation with extensions
to the @clisp rational number system.⎇

@Begin[Multiple]
The types @f[fixnum] and @f[bignum] are disjoint subtypes of @f[integer].
@Rationale{It might be thought that @f[fixnum] and @f[bignum] should
form an exhaustive partition of the type @f[integer].  This is purposely
avoided here in order to permit compatible experimentation with
extensions to the @clisp integer number system, such as the idea of
adding explicit representations of infinity or of positive and negative
infinity.⎇
@End[Multiple]

The types @f[short-float], @f[single-float], @f[double-float], and
@f[long-float] are subtypes of @f[float].  Any two of them must be
either disjoint or identical; if identical, then any other types between
them in the above ordering must also be identical to them
(for example, if @f[single-float] and @f[long-float] are identical types,
then @f[double-float] must be identical to them also).

The type @f[null] is a subtype of @f[symbol]; the only object of type
@f[null] is @nil.

The types @f[cons] and @f[null] form an exhaustive partition of the type
@f[list].

The type @f[standard-char] is a subtype of @f[string-char];
@f[string-char] is a subtype of @f[character].

The type @f[string] is a subtype of @f[vector], for @f[string]
means @f[(vector string-char)].

The type @f[bit-vector] is a subtype of @f[vector], for @f[bit-vector]
means @f[(vector bit)].

The types @f[(vector t)], @f[string], and @f[bit-vector] are disjoint.

The type @f[vector] is a subtype of @f[array]; for all types @i[x],
the type @f[(vector @i[x])] is the same as the type @f[(array @i[x] (*))].

The type @f[simple-array] is a subtype of @f[array].

The types @f[simple-vector], @f[simple-string], and
@f[simple-bit-vector] are disjoint subtypes of @f[simple-array], for they
respectively mean @f[(simple-array t (*))], @f[(simple-array string-char (*))],
and @f[(simple-array bit (*))].

The type @f[simple-vector] is a subtype of @f[vector], and indeed is
a subtype of @f[(vector t)].

@Begin[Multiple]
The type @f[simple-string] is a subtype of @f[string].
(Note that although @f[string] is a subtype of @f[vector],
@f[simple-string] is not a subtype of @f[simple-vector].)
@Rationale{The type @f[simple-vector] might better have been called
@f[simple-general-vector], but in this instance euphony and
user convenience were deemed more important to the design
of @clisp than a rigid symmetry.⎇
@End[Multiple]

The type @f[simple-bit-vector] is a subtype of @f[bit-vector].
(Note that although @f[bit-vector] is a subtype of @f[vector],
@f[simple-bit-vector] is not a subtype of @f[simple-vector].)

The types @f[vector] and @f[list] are disjoint subtypes of @f[sequence].

The types @f[hash-table], @f[readtable], @f[package], @f[pathname],
@f[stream], and @f[random-state] are pairwise disjoint.

Any two types created by @Macref[defstruct] are disjoint unless
one is a supertype of the other by virtue of
the @Kwdref[F {defstruct⎇, K {include⎇] option.

@Begin[Multiple]
An exhaustive union for the type @f[common] is formed by the types
@f[cons], @f[symbol], @f[(array @i[x])] where @i[x] is either @true or 
a subtype
of @f[common], @f[string], @f[fixnum], @f[bignum], @f[ratio],
@f[short-float], @f[single-float], @f[double-float], @f[long-float],
@f[(complex @i[x])] where @i[x] is a
subtype of @f[common],
@f[standard-char], @f[hash-table], @f[readtable], @f[package], @f[pathname],
@f[stream], @f[random-state], and all types created by the user
via @Macref[defstruct].
An implementation may not unilaterally add subtypes to
@f[common]; however, future revisions to the @clisp standard may
extend the definition of the @f[common] data type.

Note that a type such as @f[number] or @f[array] may or may
not be a subtype of @f[common], depending on whether or not the given
implementation has extended the set of objects of that type.
@End[Multiple]
@End[Itemize]